package leetcode.middle._previous;

//最大礼物的值

/**
 * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。
 * 你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。
 * 给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 */
public class MaxValue {

    public static void main(String[] args) {
        int[][] arr = new int[][]{{1,3,1},{1,5,1},{4,2,1}};
        System.out.println(new MaxValue().maxValue(arr));
    }

    public int maxValue(int[][] gird) {
        int x = gird.length;
        int y = gird[0].length;

        int[][] arr = new int[x][y];

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (i == 0 && j == 0) arr[i][j] = gird[i][j];
                else if (i == 0) {
                    arr[i][j] = gird[i][j] + arr[i][j - 1];
                } else if (j == 0) {
                    arr[i][j] = gird[i][j] + arr[i - 1][j];
                } else {
                    arr[i][j] = Math.max(gird[i][j] + arr[i - 1][j], gird[i][j] + arr[i][j - 1]);
                }
            }
        }

        return arr[x-1][y-1];
    }
}
